package LeetCode.exercise;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class LC_18 {
    public static void main(String[] args) {
        int[] nums = {2,2,2,2,2};
        System.out.println(threeSum(nums,8));
    }
    public static List<List<Integer>> threeSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        int a = 0;
        while (a < nums.length-3 ){
            for (int b = a + 1; b < nums.length-2;){
                int left = b + 1;
                int right = nums.length - 1;
                while (left < right){
                    if(nums[left] + nums[right] == (long)target-nums[a]-nums[b]){
                        lists.add(new ArrayList<Integer>(Arrays.asList
                                (nums[a], nums[b], nums[left], nums[right])));
                        left++;
                        right--;
                        while (nums[left] == nums[left-1] && left < right){
                            left++;
                        }
                        while (nums[right] == nums[right+1] && left < right){
                            right--;
                        }
                    } else if(nums[left] + nums[right] > target-nums[a]-nums[b]){
                        right--;
                    } else {
                        left++;
                    }
                }
                b++;
                while (b < nums.length && nums[b] == nums[b-1]){
                    b++;
                }
            }
            a++;
            while (a < nums.length && nums[a] == nums[a-1]){
                a++;
            }
        }
        return lists;
    }
}
